package com.chilly.vidio.study.leetcode;

import java.util.Arrays;

/**
 * 75. 颜色分类
 * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，
 * 并按照红色、白色、蓝色顺序排列。
 * <p>
 * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 * 示例 1：
 * 输入：nums = [2,0,2,1,1,0]
 * 输出：[0,0,1,1,2,2]
 *
 * @author Chilly Cui
 * @createDate 2021/2/28
 */
public class No75SortColors {
    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] nums = {2, 0, 2, 1, 1, 0};
        // expect [0, 0, 1, 1, 2, 2]

        //暴力解法
        //Arrays.sort(nums);

        solution.sortColors21(nums);
        System.out.println(Arrays.toString(nums));
        //[0, 0, 1, 1, 2, 2]
    }

    static class Solution {
        //sortColors2 优化点：颜色分类不是3，而是n个时，如何优化代码
        public void sortColors22(int[] nums) {

        }

        //sortColors2 优化点：对nums数组进行一次循环，完成排序
        //三路快速排序：Quick Sort 3 Ways
        public void sortColors21(int[] nums) {
            //nums[0...zero] == 0
            //nums[two...n-1] == 2
            int zero = -1;
            int two = nums.length;

            for (int i = 0; i < two; ) {
                if (nums[i] == 1) {
                    i++;
                } else if (nums[i] == 2) {
                    two--;
                    swap(nums, i, two);
                } else {
                    //Assert.assertTrue(nums[i] == 0);
                    zero++;
                    swap(nums, zero, i);
                    i++;
                }
            }
        }

        private void swap(int[] nums, int left, int right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }

        //时间复杂度 O(n)
        //空间复杂度 O(1)
        public void sortColors2(int[] nums) {
            int[] count = new int[3]; //存放0,1,2三个元素的频率
            for (int num : nums) {
                //Assert.assertTrue(num >= 0 && num <= 2);
                count[num]++;
            }
            int idx = 0;
            for (int i = 0; i < count[0]; i++) {
                nums[idx++] = 0;
            }
            for (int i = 0; i < count[1]; i++) {
                nums[idx++] = 1;
            }
            for (int i = 0; i < count[2]; i++) {
                nums[idx++] = 2;
            }
        }

        /**
         * 计数排序：分别统计0，1,2的元素个数
         *
         * @param nums
         */
        public void sortColors(int[] nums) {
            int red0 = 0;
            int white1 = 0;
            int blue2 = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == 0) {
                    red0++;
                } else if (nums[i] == 1) {
                    white1++;
                } else {
                    blue2++;
                }
            }

            for (int i = 0; i < red0; i++) {
                nums[i] = 0;
            }
            for (int i = red0; i < red0 + white1; i++) {
                nums[i] = 1;
            }
            for (int i = red0 + white1; i < nums.length; i++) {
                nums[i] = 2;
            }
        }
    }
}
